# -*- coding: utf-8 -*-
import collections;

# 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串
# 示例:

# 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
# 输出:
# [
#   ["ate","eat","tea"],
#   ["nat","tan"],
#   ["bat"]
# ]

# 说明：
# 所有输入均为小写字母
# 不考虑答案输出的顺序

# class Solution(object):
#     def groupAnagrams(self, strs):
#         """
#         :type strs: List[str]
#         :rtype: List[List[str]]
#         """
#         rtn = collections.defaultdict(list);

#         for i in range(len(strs)):
#             signal = list(strs[i]);
#             rtn[tuple( sorted(signal) )].append(strs[i]);

#         return rtn.values();



# 更好的解决方法使用计数进行分类
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        rtn = collections.defaultdict(list);

        for i in range(len(strs)):
            key = [0] * 26;
            for c in strs[i]:
                key[ord(c) - ord("a")] += 1;
            rtn[tuple(key)].append(strs[i]);

        return rtn.values();

t = Solution();
print t.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]);